package 二叉树;

import 我的JDK基础数据结构.HashMap.HashMap;

import java.util.Map;

public class JZ07重建二叉树 {

    /**
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。
     * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     *
     * 例如，给出
     * 前序遍历 preorder = [3,9,20,15,7]
     * 中序遍历 inorder = [9,3,15,20,7]
     * 返回如下的二叉树：
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     *  
     * 限制：
     * 0 <= 节点个数 <= 5000
     */

    private int[] preorder;
    private Map<Integer,Integer> inMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length<1){
            return null;
        }
        this.preorder=preorder;

        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        this.inMap =map;

        /**
         * 前序遍历 preorder = [3,9,20,15,7]
         * 中序遍历 inorder = [9,3,15,20,7]
         */

        return createTreeNode(0,preorder.length-1,0,inorder.length-1);
    }

    private TreeNode createTreeNode(int pLeft,int pRight,int iLeft,int iRight) {

        if(pRight<pLeft||iRight<iLeft){
            return null;
        }

        TreeNode root=new TreeNode(preorder[pLeft]);

        int inIndex=inMap.get(preorder[pLeft]);

        root.left=createTreeNode(pLeft+1,pLeft+(inIndex-iLeft),
                iLeft,inIndex-1);
        root.right=createTreeNode(pLeft+(inIndex-iLeft)+1,pRight,
                inIndex+1,iRight);

        return root;
    }

    public static void main(String[] args) {
        int[] arr1={3,9,20,15,7};
        int[] arr2={9,3,15,20,7};
        JZ07重建二叉树 jz=new JZ07重建二叉树();
        TreeNode treeNode = jz.buildTree(arr1, arr2);
        treeNode.printNode();
    }

}
